package com.lun.easy;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import com.lun.util.BinaryTree.TreeNode;

public class BinaryTreeInorderTraversal {
	
	//方法一：递归法
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorderTraversal(root, result);
        return result;
    }
    
    private void inorderTraversal(TreeNode node, List<Integer> result) {
    	if(node == null) return;
    	
    	inorderTraversal(node.left, result);
    	result.add(node.val);
    	inorderTraversal(node.right, result);
    }
    
    //方法二：迭代法
    public List<Integer> inorderTraversal2(TreeNode root) {
    	List<Integer> result = new ArrayList<>();
    	if(root == null) return result;
    	
    	LinkedList<TreeNode> stack = new LinkedList<>();
    	TreeNode p = root;
    	
    	while(!stack.isEmpty() || p != null) {
    		if(p != null) {
    			stack.push(p);
    			p = p.left;
    		}else {
    			TreeNode node = stack.pop();
    			result.add(node.val);
    			p = node.right;
    		}
    	}
    	
    	return result;
    }
}
